﻿#pragma once
// 公共头文件

#include <iostream>
#include <vector>
#include <ctime>
#include <thread>
#include <stdlib.h>
#include <assert.h>
#include "log.hpp"  // 自定义的日志文件
#include <mutex>
#include <algorithm>
#include <unordered_map>

static const size_t MAX_BYTES = 256 * 1024;  // ThreadCache 所被允许的最大字节数
static const size_t NFREELIST = 208;		 // 哈希桶总共个数
static const size_t NPAGES = 129;  // 假设page单位为8kb，那么给最大的分配256kb - 分配四块足矣，也可以随意调整
static const size_t PAGE_SHIFT = 13;  // 假定一页大概8kb，偏移量就是13

// x86 x64环境下进程地址空间大小的不同，分配不同的数据类型
#ifdef _WIN64
	typedef unsigned long long span_t;
#elif _WIN32
	typedef unsigned int span_t;
#else
	// Linux环境下
#endif //  _WIN64

#ifdef _WIN32
#include <Windows.h>
#else
// Linux

#endif

// 利用系统系统调用接口申请以页为单位的内存块 利用条件编译实现跨平台
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);  // 一页为8kb kpage为页数 8kb = 8 * 1024字节 kpage * 2 ^ 13  向高位移动13位即可  分配类型 内存的初始保护属性
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();  // 未能分配请求的存储空间时抛出的异常类型

	return ptr;
}

// 利用系统系统调用接口释放申请的内存块 利用条件编译实现跨平台
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// linux下brk mmap等
#endif
}

/*公共函数*/

// 取此对象的前指针大小字节，可读可写(写必须加引用哦)
static void*& NextObj(void* obj)
{
	return *(void**)obj;  // 可同时满足x32和x64位系统的需求
}

/*公共类*/

// 自由链表 - 管理切分好的小对象
class FreeList
{
public:
	void Push(void* obj);  // 向此自由链表头插入结点
	void* Pop();  // 此自由链表头删结点
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t& GetMaxSize()
	{
		return _maxSize;
	}
	size_t Size()
	{
		return _size;
	}
	void PushRange(void* strat, void* end, size_t n);
	void PopRange(void*& start, void*& end, size_t n);
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;  // 被调用的频率，每次申请对应内存数据都会+1表示多申请_maxSize - 1个内存块用于threadcache
	size_t _size = 0;  // 记录实时个数
};

// 计算对象大小的对齐映像规则
class SizeClass
{
	// 简化tcmalloc的对齐规则 - 保持每个区域最多只有10%的内存浪费
	// 申请字节数范围	              对齐字节数          哈希桶编号			     注意对齐字节数为对应数的倍数(比如如果是9byte 对应字节数为16byte)
	// [1, 128]2^7                8byte              freeList[0, 15]   16
	// [128+1, 1024]2^10          16byte             freeList[16, 71]  56
	// [1024+1, 8*1024]2^13       128byte		     freeList[72, 127] 56
	// [8*1024+1, 64*1024]2^16    1024byte           freeList[128, 183]56
	// [64*1024+1, 256*1024]2^18  8*1024byte         freeList[184, 207]24
public:
	static size_t _RoundUp(size_t size, size_t alignNum);  // 向上对齐子函数 申请的字节数+对齐数
	static size_t RoundUp(size_t size);  // 向上对齐
	static size_t _Index(size_t size, size_t alignShift);  // 索引的子函数 申请的字节数+对齐数的位数(2^n)
	static size_t Index(size_t size);  // 对应哈希桶的索引

	static size_t IndexAlignSize(size_t alignSize)
	{
		static int groupArray[4] = { 16, 72, 128, 184 };  // 前四个区间的哈希桶个数
		// 给的参数是一个已经对齐了的对齐数
		if (alignSize <= 128) return alignSize / 8 - 1;
		else if (alignSize <= 1024) return groupArray[0] + ((alignSize - 128) / 16 - 1);
		else if (alignSize <= 8 * 1024) return groupArray[1] + ((alignSize - 1024) / 128 - 1);
		else if (alignSize <= 64 * 1024) return groupArray[2] + ((alignSize - 8 * 1024) / 1024 - 1);
		else if (alignSize <= 256 * 1024) return groupArray[3] + ((alignSize - 64 * 1024) / (8 * 1024) - 1);
		else return -1;
	}
	static size_t NumMoveSize(size_t size);  // 返回对应大小的上限
	static size_t NumMovePage(size_t size);  // 返回对应大小应该获取多大page的span
};

// span跨度的结构定义 用于centralcache中数据元素的描述与组织
struct span
{
	span_t _pageld = 0;  // 页号
	size_t _n = 0;  // 页的数量 代表此span的大小

	span* _next = nullptr;
	span* _prev = nullptr;

	size_t _useCount = 0;  // 分位小块分出去的个数
	void* _freeList = nullptr;  // 分好子块的自由链表
	
	bool _isUse = false;  // 初始定义false标识其span在pagecache层，没有被后面层使用或者申请
	size_t _objSize = 0;  // 切分对应span的时候的对应内存块大小，方便释放的时候通过span可以找到其大小
};

// span结构的带头双向循环链表
class SpanList
{
public:
	SpanList() :_head(nullptr)
	{
		_head = new span;
		assert(_head);
		_head->_next = _head;
		_head->_prev = _head;
	}

	void Insert(span* pos, span* newSpan)
	{
		assert(pos && newSpan);
		span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		pos->_prev = newSpan;
		newSpan->_next = pos;
	}

	void Erase(span* pos)
	{
		assert(pos && (pos != _head));

		span* next = pos->_next;
		pos->_prev->_next = next;
		next->_prev = pos->_prev;
	}

	void HeadInsert(span* newSpan)
	{
		Insert(Begin(), newSpan);
	}

	span* Begin()
	{
		return _head->_next;
	}

	span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	span* PopFront()
	{
		// 头删
		if (!Empty())
		{
			span* tmp = _head->_next;
			Erase(tmp);  // 这里相当于只是在双链表中将其丢出去而已
			return tmp;
		}
		return nullptr;
	}

private:
	span* _head;
public:
	std::mutex _mtx;  // 互斥锁准备好 - 桶锁
};

/*方法的定义*/

// FreeList////
void FreeList::Push(void* obj)
{
	assert(obj);  // 插入结点不可为空

	NextObj(obj) = _freeList;
	_freeList = obj;
	_size++;
}
void* FreeList::Pop()
{
	assert(_freeList);  // 删除结点不可为空

	void* obj = _freeList;
	_freeList = NextObj(_freeList);
	_size--;
	return obj;
}
// 插入连续的一串
void FreeList::PushRange(void* strat, void* end, size_t n)
{
	assert(strat && end);
	NextObj(end) = _freeList;
	_freeList = strat;

	_size += n;
}
// 弹出连续的一串
void FreeList::PopRange(void*& start, void*& end, size_t n)
{
	assert(_size >= n);  // 如果不是这样说明外面的逻辑错误了

	start = _freeList;
	end = start;
	for (size_t i = 0; i < n - 1; i++)
	{
		end = NextObj(end);
	}
	_freeList = NextObj(end);
	_size -= n;
	NextObj(end) = nullptr;  // 截断准备上传
}

// SizeClass////
inline size_t SizeClass::_RoundUp(size_t size, size_t alignNum)
{
	// 常规思路:
	//if (size % alignNum != 0) return (size / alignNum + 1) * alignNum;
	//else return size;
	// 位运算  因为此处需要频繁的调用，所以需要位运算进行优化效率
	return ((alignNum + size - 1) & ~(alignNum - 1));  // 比如8：XXX & ...1000  -> XX1000 (X表示1或者0)
}
inline size_t SizeClass::RoundUp(size_t size)  // 注意inline必须在定义的时候告知，才会被写入符号表
{
	if (size <= 128) return _RoundUp(size, 8);
	else if (size <= 1024) return _RoundUp(size, 16);
	else if (size <= 8 * 1024) return _RoundUp(size, 128);
	else if (size <= 64 * 1024) return _RoundUp(size, 1024);
	else if (size <= 256 * 1024) return _RoundUp(size, 8 * 1024);
	else
	{
		//assert(false);
		return _RoundUp(size, 1 << PAGE_SHIFT);
	}
}
inline size_t SizeClass::_Index(size_t size, size_t alignShift)
{
	// 常规思路:
	//alignShift = (size_t)1 << alignShift;  // 还原为对齐数
	//if (size % alignShift == 0) return size / alignShift - 1;
	//else return size / alignShift;
	// 位运算 算对应区域对齐数所映射的索引
	return ((size + ((size_t)1 << alignShift) - 1) >> alignShift) - 1;  // 左边可以理解为 (size + 对齐数 - 1) / 对齐数 - 1
}
inline size_t SizeClass::Index(size_t size)
{
	static int groupArray[4] = { 16, 72, 128, 184 };  // 前四个区间的哈希桶个数
	if (size <= 128) return _Index(size, 3);
	else if (size <= 1024) return _Index(size - 128, 4) + groupArray[0];
	else if (size <= 8 * 1024) return _Index(size - 1024, 7) + groupArray[1];
	else if (size <= 64 * 1024) return _Index(size - 8 * 1024, 10) + groupArray[2];
	else if (size <= 256 * 1024) return _Index(size - 64 * 1024, 13) + groupArray[3];
	else
	{
		assert(false);
		return -1;
	}
}
// 返回对应数据类型的一个上限算法
inline size_t SizeClass::NumMoveSize(size_t size)
{
	size_t num = MAX_BYTES / size;
	if (num < 2) num = 2;  // 最低为2
	else if (num > 512) num = 512;  // 最多不超过512个
	return num;
}
// 返回对应数据类型一次申请多少page大小大块的span
inline size_t SizeClass::NumMovePage(size_t size)
{
	size_t batchNum = NumMoveSize(size);
	size_t bytes = batchNum * size;  // 字节大小
	size_t page = bytes >> PAGE_SHIFT;  // 向低位偏移，查看需要申请的页个数
	if (page == 0) page = 1;  // 至少申请1页
	return page;
}
